As is known in the art, a network includes a plurality of processing sites generally referred to as stations or nodes connected by one or more physical or wireless and/or logical connections. When the connections establish transmission of a signal in one direction between the nodes, the connections are generally referred to as links. Each node typically performs a switching function and one or more additional functions.
In some network applications, nodes can transmit and receive, but cannot transmit and receive at the same time. In such applications, a sender in a link wants to transmit M data packets at a given link data rate R and the channel is modeled as a packet erasure channel. To transmit data packets at a desirable rate, network coding (also sometimes referred to as coded packet networks) may be used.
Network coding considers the nodes to have a set of functions that operate upon received or generated data packets. Today's networks would represent a subset of the coded packet networks, in which each node has two main functions: forwarding and replicating a packet. A classical network's task is to transport packets provided by the source nodes unmodified. In contrast, network coding considers information as an algebraic entity, on which one can operate.
Network coding research originally studied throughput performance without delay considerations for the transmitted information. Initial work in this area considered a channel with no erasures and, therefore, no need for feedback. Later work showed that linear codes over a network are sufficient to implement any feasible multicast connection, again considering a channel with no erasures. In both of these cases, the nodes are considered to transmit a linear combination of the packets previously received.
Still other systems utilize linear codes generated randomly in a network. It has been shown that such systems achieve multicast capacity in a non-erasure channel.
For networks with packet erasures, two approaches have been used. The first approach uses block transmissions. With respect to wireless networks, it has been shown that linear codes achieve capacity in the network. A second approach relies on rateless codes, i.e. transmitting coded data packets until a receiver sends an acknowledgement stating that all data packets have been decoded successfully.
It has also been shown that random linear network coding in lossy networks can achieve packet-level capacity for both single unicast and single multicast connections and for models of both wireline and wireless networks.
Still other systems utilize network codes that preserve the communication efficiency of a random linear code, while achieving better computational efficiency. Some prior art work presents a random linear coding scheme for packet streams considering nodes with a fixed, finite memory, establishing a trade-off between memory usage and achievable rate.
Some prior art references have studied delay performance gains and their scaling laws for network coding with and without channel side information, respectively. The focus of some of this work is on transmission of large files in a rateless fashion, i.e. minimal feedback to indicate that the information has been successfully decoded. In some references, the performance of network coding for a tree-based multicast problem is studied and compared to various Automatic Repeat reQuest (ARQ) and Forward Error Correcting (FEC) techniques. The expected number of transmissions per packet is used as the performance metric. For network coding, this reference assumes reliable and instantaneous feedback to acknowledge a correct decoding of all data packets. Note that the focus of these references has been on either throughput or delay performance, usually considering minimal feedback.
Finally, some prior art systems couple the benefit of network coding and ARQ by acknowledging degrees of freedom instead of original data packets to show that queue size in a node follows degrees of freedom.